#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <utility>
#include <algorithm>

using namespace std;

// 图的邻接表表示
class Graph {
private:
    int V; // 顶点数
    vector<vector<pair<int, int>>> adj; // 邻接表，存储<目标顶点, 权值>

public:
    Graph(int V); // 构造函数
    void addEdge(int u, int v, int weight); // 添加带权边
    void dijkstra(int src); // Dijkstra算法
};

// 构造函数
Graph::Graph(int V) : V(V), adj(V) {}

// 添加带权边
void Graph::addEdge(int u, int v, int weight) {
    if (u >= 0 && u < V && v >= 0 && v < V) {
        adj[u].push_back({v, weight});
    } else {
        cerr << "错误: 边 (" << u << ", " << v << ") 的顶点超出范围 [0, " << V-1 << "]" << endl;
    }
}

// Dijkstra算法
void Graph::dijkstra(int src) {
    vector<int> dist(V, numeric_limits<int>::max()); // 距离数组
    vector<bool> visited(V, false); // 访问标记数组
    vector<int> parent(V, -1); // 记录最短路径的前驱节点

    dist[src] = 0;

    for (int count = 0; count < V - 1; ++count) {
        int u = -1;
        for (int i = 0; i < V; ++i) {
            if (!visited[i] && (u == -1 || dist[i] < dist[u])) {
                u = i;
            }
        }

        visited[u] = true;

        for (const auto &edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (!visited[v] && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                parent[v] = u;
            }
        }
    }

    // 打印结果
    cout << "顶点\t距离\t最短路径" << endl;
    for (int i = 0; i < V; ++i) {
        if (i != src) {
            cout << src << " -> " << i << "\t";
            if (dist[i] == numeric_limits<int>::max()) {
                cout << "∞\t(不存在)" << endl;
            } else {
                cout << dist[i] << "\t(";
                int j = i;
                vector<int> path;
                while (j != -1) {
                    path.push_back(j);
                    j = parent[j];
                }
                reverse(path.begin(), path.end());
                for (size_t k = 0; k < path.size(); ++k) {
                    cout << path[k];
                    if (k != path.size() - 1) {
                        cout << ", ";
                    }
                }
                cout << ")" << endl;
            }
        }
    }
}

int main() {
    int V, E, src;

    // 输入顶点数
    cout << "请输入顶点数: ";
    cin >> V;
    if (V <= 0) {
        cerr << "错误: 顶点数必须大于 0" << endl;
        return 1;
    }

    // 创建图
    Graph g(V);

    // 输入边数
    cout << "请输入边数: ";
    cin >> E;
    if (E < 0) {
        cerr << "错误: 边数不能为负数" << endl;
        return 1;
    }

    // 输入边的信息
    cout << "请输入边的信息 (每行三个整数: 起点 终点 权值):" << endl;
    for (int i = 0; i < E; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        g.addEdge(u, v, weight);
    }

    // 输入源点
    cout << "请输入源点: ";
    cin >> src;

    cout << "从源点 " << src << " 到其他顶点的最短路径:" << endl;
    g.dijkstra(src);

    return 0;
}